package com.aqie.medium.binarySearchTree;

import com.aqie.easy.structure.TreeNode;

import java.util.Stack;

/**
 * todo
 * 1008 先序遍历构造二叉树
 * 根 左 右
 */
public class BstFromPreorder {
    /**
     * 递归实现
     * @param preorder
     * @return
     */
    public TreeNode bstFromPreorder(int[] preorder) {
        TreeNode root  = null;
        for (int i = 0; i < preorder.length; i++){
            root = add(root, preorder[i]);
        }
        return root;
    }

    private TreeNode add(TreeNode root, int num) {
        if (root == null) return new TreeNode(num);
        if (root.val > num) root.left = add(root.left, num);
        else root.right = add(root.right, num);
        return root;
    }

    public TreeNode bstFromPreorder2(int[] preorder) {
        if (preorder.length == 0) return null;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode res = new TreeNode(preorder[0]);
        stack.push(res);
        for (int i = 1; i < preorder.length; i++){
            TreeNode root = stack.peek();
            if (preorder[i] < root.val){
                root.left = new TreeNode(preorder[i]);
                stack.push(root.left);
            }else {
                TreeNode cur = stack.pop();
                while (!stack.isEmpty() && stack.peek().val < preorder[i]){
                    cur = stack.pop();
                }
                cur.right = new TreeNode(preorder[i]);
                stack.push(cur.right);
            }
        }
        return res;
    }
}
